1. Technical Field of the Invention
This invention relates to digital parallel processing systems, wherein a plurality of nodes communicate via messages sent over an interconnection network. In particular, this invention provides a method and apparatus for creating scalable, non-blocking networks.
2. Background Art
Clos has set the basis for non-blocking networks in his paper, "A study of Non-blocking Switching Networks", March 1953; Bell System Technical Journal (vol.32, pp 406-24). While Clos solves the blocking problem, his solution requires for larger networks a very large number of switch chips. For example, for a network with 32,000 nodes, CLOS's solution requires 39.5 switch chips per node or 1,294,336 total chips to build the network. There is a need, therefore, in the art to provide a more efficient solution to the blocking problem.
The CLOS non-blocking multi-stage network includes input, middle, and output stages. CLOS requires the three stages to be of variable size and to have a variable number of inputs and outputs to each stage. A high development cost is required to build a network using a multiplicity of various sized switch chips. In this case variable numbers of inputs and outputs can be obtained by simply not using (wasting) some of the input and output ports to the switch chip. There is, therefore, a need in the art for a switch chip of one given size to be used in constructing all three stages, one which avoids the inefficiency of wasting switch ports.
This invention relates to digital parallel processing systems, wherein a plurality of nodes communicate via messages sent over an interconnection network. Each node usually interfaces to the network via a network adapter. There is a demand for larger networks requiring non-blocking. Non-blocking means that two idle nodes attached to the network can always be connected through the network, and the network will never prevent the connection. For instance, in the extreme case where a network supports 32,000 nodes, if 31,998 nodes are connected to each other, the network (if non-blocking) will always provide at least one idle path whereby the last two nodes can be connected. The characteristic of being non-blocking and scalable to a large number of nodes is very challenging.
It is, therefore, an object of the invention to provide a network switching structure and method which reduce the complexity of non-blocking networks.
It is a further object of this invention to provide a method and apparatus for creating scalable, non-blocking networks with an order of magnitude less hardware than the state-of-the-art approach.